<?php

namespace app\binarysearchtree\controller;
/**
 * 三、如何设计一个二叉树的数据结构
1、二叉查找树(BST)由节点组成，所以可以先定义一个节点类，用来保存节点数据和其他节点的链接（left和right）；
2、再定义一个二叉查找树类，让类只包含一个数据成员:一个表示二叉查找树根节点的Node对象。该类的构造函数将根节点初始化为 null，以此创建一个空节点；
3、BST 先要有一个 insert() 方法，用来向树中加入新节点；
4、其次检查 BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法到此就完成了，否则，进入下一步；
5、如果待插入节点不是根节点，那么就需要准备遍历 BST，找到插入的适当位置。该过程类似于遍历链表。用一个变量存储当前节点，一层层地遍历 BST；
6、进入 BST 以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循环。查找正确插入点的算法如下：
（1）设根节点为当前节点。
（2）如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第 4 步。
（3）如果当前节点的左节点为 null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
（4）设新的当前节点为原节点的右节点。
（5）如果当前节点的右节点为 null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
 * Class Tree
 * @package app\binarysearchtree\controller
 */
class Tree
{
   private $root;
   public function __construct()
   {
       $this->root = null;
   }

    /**
     * while循环实现
     * @param $data
     * @return bool
     */
   public function insert($data)
   {
       if(!$this->root){
           $this->root = new Node($data);
       }else{
            $current = $this->root;
            $node = new Node($data);
            while ($node->data <= $current->data){
                if(is_null($current->left)) {
                    $current->left = $node;
                    return true;
                }
                $current = $current->left;
            }
            while ($node->data > $current->data){
                if(is_null($current->right)) {
                    $current->right = $node;
                    return true;
                }
                $current = $current->right;
            }
       }
   }

}